#include <iostream>
#include <stdlib.h>
#include <queue>

struct BTNode{
	int data;
	struct BTNode *left;
	struct BTNode *right;
};
//给定二叉树 [3,9,20,null,null,15,7]
void createTree(BTNode *root)
{   
    root->data = 3;
    struct BTNode *n1, *n2, *n3, *n4;
    n1 = (BTNode*)malloc(sizeof(BTNode));
    n2 = (BTNode*)malloc(sizeof(BTNode));
    n3 = (BTNode*)malloc(sizeof(BTNode));
    n4 = (BTNode*)malloc(sizeof(BTNode));
    root->left = n1;
    root->right = n2;
    n1->data = 9;
    n1->left = NULL;
    n1->right = NULL;
    n2->data = 20;
    n3->data = 15;
    n4->data = 7;
    n2->left = n3;
    n2->right = n4;
    n3->left = NULL;
    n3->right = NULL;
    n4->right = NULL;
    n4->left = NULL;
}
//找到这棵二叉树的最小高度，使用BFS
int minDepth(BTNode *root)
{
    if (root == NULL) return 0;
    std::queue<BTNode*> q;
    q.push(root);
    int depth = 1;
    struct BTNode *p;
    while (!q.empty())
    {
        int n = q.size();
        for (int i = 0; i < n; i++)
        {
            p = q.front();
            q.pop();
            /*判断是否达到终点*/
            if (p->left == NULL && p->right == NULL)
            {
                //第一个达到终点的叶子结点的深度就是这棵树的最小深度。
                return depth;
            }
            if (p->left != NULL)
                q.push(p->left);
            if (p->right != NULL)
                q.push(p->right); 
        }
        depth++;
    }
    return depth;   
}
int main()
{
    using namespace std;
    struct BTNode *root;
    root = (BTNode*)malloc(sizeof(BTNode));
    createTree(root);
    cout << minDepth(root) << endl;
    return 0;
}